package com.acane.instagram.utils;

import java.util.*;

public class ACTrie {
    private final ACTrieNode root = new ACTrieNode();
    private boolean built = false;

    // AC节点定义
    private static class ACTrieNode {
        Map<Character, ACTrieNode> children = new HashMap<>();
        ACTrieNode fail;
        boolean isEnd;
        int length; // 敏感词长度（用于快速替换）
    }

    public ACTrie(List<String> words) {
        buildTrie(words);
        buildFailPointer();
        this.built = true;
    }

    // 构建Trie树
    private void buildTrie(List<String> words) {
        for (String word : words) {
            if (word == null || word.isEmpty()) {
                continue;
            }
            ACTrieNode node = root;
            for (char c : word.toCharArray()) {
                node.children.putIfAbsent(c, new ACTrieNode());
                node = node.children.get(c);
            }
            node.isEnd = true;
            node.length = word.length();
        }
    }

    // 构建失败指针（BFS层序构建）
    private void buildFailPointer() {
        Queue<ACTrieNode> queue = new LinkedList<>();
        
        // 第一层失败节点指向root
        root.fail = null;
        for (ACTrieNode child : root.children.values()) {
            child.fail = root;
            queue.offer(child);
        }

        // 构建后续层失败指针
        while (!queue.isEmpty()) {
            ACTrieNode curr = queue.poll();
            
            for (Map.Entry<Character, ACTrieNode> entry : curr.children.entrySet()) {
                char c = entry.getKey();
                ACTrieNode child = entry.getValue();
                ACTrieNode failTo = curr.fail;
                
                while (failTo != null && !failTo.children.containsKey(c)) {
                    failTo = failTo.fail;
                }
                
                child.fail = (failTo == null) ? root : failTo.children.getOrDefault(c, root);
                child.isEnd |= child.fail.isEnd; // 继承失效路径的敏感词状态
                queue.offer(child);
            }
        }
    }

    // 检测敏感词（返回是否包含）
    public boolean containsSensitiveWord(String text) {
        if (!built || text == null || text.isEmpty()) {
            return false;
        }

        ACTrieNode curr = root;
        char[] chars = text.toCharArray();
        
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            
            // 快速失败跳转逻辑
            while (curr != root && !curr.children.containsKey(c)) {
                curr = curr.fail;
            }
            
            curr = curr.children.getOrDefault(c, root);
            
            // 检查当前节点及失效链上的结束标记
            ACTrieNode temp = curr;
            while (temp != null) {
                if (temp.isEnd) {
                    return true;
                }
                temp = temp.fail;
            }
        }
        return false;
    }

    // 获取所有敏感词（用于替换场景）
    public List<String> findSensitiveWords(String text) {
        List<String> results = new ArrayList<>();
        if (!built) {
            return results;
        }

        ACTrieNode curr = root;
        char[] chars = text.toCharArray();
        
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            
            while (curr != root && !curr.children.containsKey(c)) {
                curr = curr.fail;
            }
            
            curr = curr.children.getOrDefault(c, root);
            
            ACTrieNode temp = curr;
            while (temp != null) {
                if (temp.isEnd) {
                    int start = i - temp.length + 1;
                    results.add(text.substring(start, i + 1));
                }
                temp = temp.fail;
            }
        }
        return results;
    }
}